typedef int QDataType;

typedef struct QueueNode

{

    struct QueueNode* next;

    QDataType data;

}QNode;



typedef struct Queue

{

    QNode* head;

    QNode* tail;

    int size;

}Que;



void QueueInit(Que* pq);

void QueueDestroy(Que* pq);

void QueuePush(Que* pq, QDataType x);

void QueuePop(Que* pq);

QDataType QueueFront(Que* pq);

QDataType QueueBack(Que* pq);

bool QueueEmpty(Que* pq);

int QueueSize(Que* pq);

void QueueInit(Que* pq)

{

    assert(pq);



    pq->head = pq->tail = NULL;

    pq->size = 0;

}



void QueueDestroy(Que* pq)

{

    assert(pq);



    QNode* cur = pq->head;

    while (cur)

    {

        QNode* next = cur->next;

        free(cur);

        cur = next;

    }



    pq->head = pq->tail = NULL;

    pq->size = 0;

}



void QueuePush(Que* pq, QDataType x)

{

    assert(pq);



    QNode* newnode = (QNode*)malloc(sizeof(QNode));

    if (newnode == NULL)

    {

        perror("malloc fail");

        exit(-1);

    }



    newnode->data = x;

    newnode->next = NULL;



    if (pq->tail == NULL)

    {

        pq->head = pq->tail = newnode;

    }

    else

    {

        pq->tail->next = newnode;

        pq->tail = newnode;

    }



    pq->size++;

}



void QueuePop(Que* pq)

{

    assert(pq);

    assert(!QueueEmpty(pq));



    if (pq->head->next == NULL)

    {

        free(pq->head);

        pq->head = pq->tail = NULL;

    }

    else

    {

        QNode* next = pq->head->next;

        free(pq->head);

        pq->head = next;

    }



    pq->size--;

}



QDataType QueueFront(Que* pq)

{

    assert(pq);

    assert(!QueueEmpty(pq));



    return pq->head->data;

}



QDataType QueueBack(Que* pq)

{

    assert(pq);

    assert(!QueueEmpty(pq));



    return pq->tail->data;

}



bool QueueEmpty(Que* pq)

{

    assert(pq);



    return pq->head == NULL;

}



int QueueSize(Que* pq)

{

    assert(pq);



    return pq->size;

}



typedef struct {

    Que q1;

    Que q2;



} MyStack;





MyStack* myStackCreate() {

    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));

    QueueInit(&pst->q1);

    QueueInit(&pst->q2);

    return pst;



}



void myStackPush(MyStack* obj, int x) {

    if (!QueueEmpty(&obj->q1))

    {

        QueuePush(&obj->q1, x);

    }

    else {

        QueuePush(&obj->q2, x);

    }

}



int myStackPop(MyStack* obj) {

    Que* empty = &obj->q1;

    Que* nonempty = &obj->q2;

    if (!QueueEmpty(&obj->q1))

    {
        empty = &obj->q2;

        nonempty = &obj->q1;



    }

    while (QueueSize(nonempty) > 1)

    {

        QueuePush(empty, QueueFront(nonempty));

        QueuePop(nonempty);

    }

    int top = QueueFront(nonempty);

    QueuePop(nonempty);

    return top;

}



int myStackTop(MyStack* obj) {

    if (!QueueEmpty(&obj->q1))

    {

        return QueueBack(&obj->q1);



    }



    else

    {

        return QueueBack(&obj->q2);



    }

}



bool myStackEmpty(MyStack* obj) {

    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);

}



void myStackFree(MyStack* obj) {

    QueueDestroy(&obj->q1);

    QueueDestroy(&obj->q2);

    free(obj);





}